package com.LeeCode;

import java.util.Arrays;

/**
 * 比较字符串最小字母出现频次
 */

public class Code1170 {
    public static void main(String[] args) {
        String[] queries = {"bba", "abaaaaaa", "aaaaaa", "bbabbabaab", "aba", "aa", "baab", "bbbbbb", "aab", "bbabbaabb"};
        String[] words = {"aaabbb", "aab", "babbab", "babbbb", "b", "bbbbbbbbab", "a", "bbbbbbbbbb", "baaabbaab", "aa"};
        System.out.println(Arrays.toString(new Code1170().numSmallerByFrequency(queries, words)));

    }

    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] ans = new int[queries.length], fWords = new int[words.length];



        for (int i = 0; i < words.length; i++) {
            fWords[i] = f(words[i]);
        }
        Arrays.sort(fWords);
        for (int i = 0; i < queries.length; i++) {
            ans[i] = lowerBound(fWords, f(queries[i]) + 1);
        }

        return ans;
    }

    private int f(String word) {
        int[] cnt = new int[26];
        for (char c : word.toCharArray()) {
            cnt[c - 'a']++;
        }

        for (int i = 0; i < cnt.length; i++) {
            if (cnt[i] != 0) {
                return cnt[i];
            }
        }
        return 0;
    }

    private int lowerBound(int[] nums, int target) {
        int left = -1, right = nums.length, mid;
        while (left + 1 < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return nums.length - right;
    }
}
